\documentclass{article}
\usepackage{xltxtra}
\usepackage{ctex}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{geometry}
\usepackage{booktabs}

\makeatletter
\newcommand{\Rmnum}[1]{\expandafter\@slowromancap\romannumeral #1@}
\makeatother
\geometry{a4paper,top=1.5cm,bottom=1.5cm}

\title{Theoretical questions for Section 1}
\author{张皓祥 \\ 3200102536 强基数学2001}
\date{}

% main text
\begin{document}
\maketitle

% Question 1
\noindent \textbf{\Rmnum{1}. Consider the bisection method starting with the initial interval.}

\noindent \textbf{Sol.}

\noindent (a) Denote $a_n$ be the width of the interval at the $n$th step,then we have
$$
a_0 = 3.5-1.5 = 2 \quad a_n = \frac{1}{2}a_{n-1}(n\geq 1)
$$
According to the recurrence we have 
$$ a_n=\frac{1}{2^{n-1}} $$
Thus the width of the interval at the $n$th step is $\frac{1}{2^{n-1}}$.
\bigskip

\noindent (b) According to (a), at the $n$th step, assume the interval be 
$[x_n,y_n], y_n-x_n=\frac{1}{2^{n-1}}$. Assume the midpoint be
$M_n=\frac{x_n+y_n}{2}$. Since we know that $\tau \in [x_n,y_n]$,Thus we have
$$
|\tau-M_n|\leq max\{|x_n-M_n|,|y_n-M_n|\}=\frac{1}{2}|y_n-x_n|=\frac{1}{2^n}
$$
Thus the supremun of the distance is $\frac{1}{2^n}$.
\bigskip

% Question 2
\noindent \textbf{\Rmnum{2}. Prove that the goal is guaranteed.}

\noindent \textbf{Sol.}

Denote $[a_n,b_n]$ be the interval at the $n$th step, $k_n=b_n-a_n$ and the root
be $\tau$.By using bisection method, we know that 
$$
k_0 = b_0 - a_0, \quad k_{n+1}=\frac{1}{2}k_n(n\geq 0), \quad \tau \in [a_n,b_n]
$$
Thus we can get $k_n=\frac{1}{2^n}(b_0-a_0)$, Besides, at the $n$th step, the
 relative error is $\frac{1}{2}k_n$. Thus when the relative error is no greater 
than $\epsilon$, it's equal to
\begin{gather}
    \frac{1}{2}k_n = \frac{1}{2^{n+1}}(b_0-a_0)\leq \tau\epsilon \notag\\
    \Longleftrightarrow \quad 2^{n+1} \geq \frac{b_0-a_0}{\tau\epsilon} \notag
\end{gather}

\noindent Apply the operator $\log$ to the inequality, we have
$$
(n+1)\log 2 \geq \log\frac{b_0-a_0}{\tau \epsilon}
$$
If the inequality is true for any possible $\tau$, it need to satisfy
$$
(n+1)\log 2 \geq max_{x\in (a0,b_0)}\log\frac{b_0-a_0}{\tau \epsilon} = \log\frac{b_0-a_0}{a_0 \epsilon}
$$
The inequality is meaningful since $a_0>0$. Make the equivalent transformation, 
we can get 
$$
n \geq \frac{\log(b_0-a_0)-\log\epsilon-\log a_0}{\log 2} -1.
$$

% Question 3
\noindent \textbf{\Rmnum{3}. Organize the results of the iterations of a polynomial.}

\noindent \textbf{Sol.}

For $p(x)=4x^3-2x^2+3$, the derivation is $p'(x)=12x^2-4x$. Apply Newton's 
method for the polynomial, we have
$$
x_0=-1, \quad x_{n+1}=x_n-\frac{p(x_n)}{p'(x_n)}=x_n-\frac{4x_n^3-2x_n^2+3}{12x_n^2-4x_n}
=\frac{8x_n^3-2x_n^2-3}{4(3x_n^2-x_n)}
$$
Apply the iteration fomula to $x_n$ which is calculated by Python, we can 
oragnize the results into the table as followed:
\bigskip
\\
\resizebox{\columnwidth}{!}{\begin{tabular}{cc}
    \toprule[1.5pt]
    \makebox[0.1\textwidth][c]{$n$} & \makebox[0.9\textwidth][c]{$x_n$} \\
    \midrule[0.75pt]
    0 & -1 \\
    1 & -0.8125 \\
    2 & -0.7708041958041958 \\
    3 & -0.7688323842557605 \\
    4 & -0.7688280858696084 \\
    5 & -0.7688280858492109 \\
    6 & -0.7688280858492108 \\
    7 & -0.7688280858492109 \\
    8 & -0.7688280858492108 \\
    \bottomrule[1.5pt]
\end{tabular}}

\bigskip
By the results in the table, we can conclude that one of the zero points of 
the polynomial can be approximately represented as -0.7688280858492108.
\bigskip

% Question 4
\noindent \textbf{\Rmnum{4}. Find $C$ and $s$ satisfy the topic.}

\noindent \textbf{Sol.}

Denote the exact solution be $\alpha$, then $x_n = \alpha+e_n$. By Taylor Theorem, 
\begin{align*}
    f(\alpha) = f(x_n) +(\alpha-x_n)f'(\xi) \mbox{, $\xi$ is between $x_n$ and $\alpha$}
\end{align*}
Since $f(\alpha)=0,$ then $f(x_n)=(x_n-\alpha)f'(\xi)$. Put it into the iteration, 
we have 
\begin{align*}
e_{n+1} & =x_{n+1}-\alpha \\
 & =x_n-\frac{f(x_n)}{f'(x_0)}-\alpha \\
 & =(x_n-\alpha)-\frac{(x_n-\alpha)f'(\xi)}{f'(x_0)} \\
 & =(x_n-\alpha)(1-\frac{f'(\xi)}{f'(x_0)}) \\
 & =e_n(1-\frac{f'(\xi)}{f'(x_0)})
\end{align*}

It shows that $e_{n+1}=Ce_n^s$, where $s=1$ is constant, and $C=1-\frac{f'(\xi)}{f'(x_0)}$ 
depends on $x_n$, the given function $f$, its derivation and the real value of the root.
\bigskip

% Question 5
\noindent \textbf{\Rmnum{5}. Will the iteration $x_{n+1}=\tan^{-1}x_n$ converge?}

\noindent \textbf{Sol.}

Yes, it's converge.

Since the function $f(x)=\tan^{-1}x$ is odd, 
we only need to consider $x_0\geq 0$.

\noindent $\bullet \quad x_0=0$:

Obiviously $x_n=0$ for $\forall n \geq 0$, it's converge.

\noindent $\bullet \quad x_0>0$:

Fistly, we know that when $x\in (0,\frac{\pi}{2}), \tan x >x$. So replace 
$x$ by $\tan^{-1}x_n$, we have $x_{n+1}=\tan^{-1}x_n<\tan(\tan^{-1}x_n)=x_n$. 
which means the sequence $\{x_n\}$ is monotone decreasing. Besides, if 
$x\in(0,\frac{\pi}{2}),\tan^{-1}x>0$. It implies that the sequence has the 
lower bound.

By the monotone convergence theorem of sequence, we can conclude 
that $x_{n+1}=\tan^{-1}x_n$ converges.
\bigskip

% Question 6
\noindent \textbf{\Rmnum{6}. The value of the continued fraction.}

\noindent \textbf{Sol.}

\noindent $\bullet \quad$ Fistly, we prove the sequence of value converges.
Let $x_1=\frac{1}{p},x_2=\frac{1}{p+\frac{1}{p}},x_3=\frac{1}{p+\frac{1}{p+\frac{1}{p}}},...,$
and so forth. We conclude that $x_{n+1}=\frac{1}{p+x_n}(n\geq 1)$, and 
$x = \frac{1}{p+\frac{1}{p+\frac{1}{p+...}}}=\lim_{n\rightarrow\infty}x_n$
Since $p>1,$ we can conclude that $0<x_n<1$ for $\forall n\geq 1$. 

Now we show that $\{x_{2k-1}\}$ is monotone decreasing of $k$, and 
$\{x_{2k}\}$ is monotone increasing of $k$. $(\ast)$

Since $p<p+\frac{1}{p} \Rightarrow x_1=\frac{1}{p}>\frac{1}{p+\frac{1}{p+\frac{1}{p}}}=x_3$. 
Then $x_4=\frac{1}{p+x_3}>\frac{1}{p+x_1}=x_2$. So $(\ast)$ is correct for $k=1,2$.

If $(\ast)$ is correct for all $1\leq k \leq n$, now we prove 
$x_{2(n+1)-1}<x_{2n-1}$ and $x_{2(n+1)}>x_{2n}$.

By assumption, we can imply
\begin{gather}
    x_{2(n+1)-1}=\frac{1}{p+x_{2n}}<\frac{1}{p+x_{2(n-1)}}=x_{2n-1} \notag \\
    x_{2(n+1)}=\frac{1}{p+x_{2(n+1)-1}}>\frac{1}{p+x_{2n-1}}=x_{2n} \notag
\end{gather}

By mathmetical induction, $(\ast)$ is proved.

Since $0<x_n<1$, the sequence $\{x_{2k-1}\}$ has the lower bound and the 
sequence $\{x_{2k}\}$ has the upper bound. Use monotone convergence theorem 
of sequence, both sequences converge. 
Denote $\lim_{k\rightarrow\infty}x_{2k-1}=A,\lim_{k\rightarrow\infty}x_{2k}=B$.

$\cdot \quad x_{2k}=\frac{1}{p+x_{2k-1}}$, let $k\rightarrow\infty$, we have
\begin{equation}
    B=\frac{1}{p+A} \label{AtoB}
\end{equation}

$\cdot \quad x_{2k+1}=\frac{1}{p+x_{2k}}$, let $k\rightarrow\infty$, we have
\begin{equation}
    A=\frac{1}{p+B} \label{BtoA}
\end{equation}

Combine the two equations \ref{AtoB} and \ref{BtoA}, we can show $A=B$, 
which also implies that $\{x_n\}$ converges.
\bigskip

\noindent $\bullet \quad$ Now, we can calculate the exact value of $x$.

For $x_{n+1}=\frac{1}{p+x_n}$, let $n\rightarrow\infty$, then we have
$x=\frac{1}{p+x}$. It implies that
$$
x^2+px-1=0
$$
The solution of the equation is
$$
x_1=\frac{-p+\sqrt{p^2+4}}{2}, \quad x_2=\frac{-p-\sqrt{p^2+4}}{2}
$$
Since $p>1$ and $0<x_n<1$, the proper answer is $x=\frac{-p+\sqrt{p^2+4}}{2}$.
\bigskip

% Question 7
\noindent \textbf{\Rmnum{7}. For problem \Rmnum{2}, what if $a_0<0<b_0$?}

\noindent \textbf{Sol.}

Similarly, denote $[a_n,b_n]$ be the interval at the $n$th step, $k_n=b_n-a_n$ 
and the root be $\tau$. And we know that $k_n=\frac{1}{2^n}(b_0-a_0)$.
When the relative error is no greater than $\epsilon$, assume $\tau\neq 0$, 
it remains
\begin{gather}
    \frac{1}{2}k_n = \frac{1}{2^{n+1}}(b_0-a_0)\leq |\tau|\epsilon \notag\\
    \Longleftrightarrow \quad 2^{n+1} \geq \frac{b_0-a_0}{|\tau|\epsilon} \notag
\end{gather}

\noindent Apply the operator $\log$ to the inequality.
\begin{gather}
    (n+1)\log 2 \geq \log\frac{b_0-a_0}{|\tau| \epsilon} \notag \\
    \Longrightarrow n \geq \frac{\log(b_0-a_0)-\log\epsilon-\log |\tau|}{\log 2} -1 \notag
\end{gather}

If we need to find the number which can ensure the inequality is true. 
we need to find the upper bound of $-\frac{\log|\tau|}{\log 2}$. It is equivalent 
to find the lower bound of $\log|\tau|$. However, when $|\tau|\rightarrow 0$, 
$\log|\tau|\rightarrow-\infty$, it implies that $n\geq +\infty$, which is rediculous.

Thus when $a_0<0<b_0$, the relative error will not be an appropriate measure.

\end{document}